#-*-coding:utf-8-*-
from fileoperate import FileOperate
from myoperate import DictOperate,Listoperate
import pickle
'''
This module is used to encode the str by using modified huffman code
@Author liuhucheng
@Timer 22/05/2012 09:42
find bug the GenerateCode didn't work well.can't code the str in a proper way.
'''

class Huffman:
    '''
    Modified Huffman
    '''
    def __init__(self):
        pass

    def GenerateCode(self,liststr):
        '''
        To generate the Huffman code.
        dictlist is a dict type variety
        it look like {'01':213342},the key value refer to the time it was found in the str.
        '''
        #liststr = liststr[:-1]
        #l = liststr.split('\0')
        #l = [x.strip() for x in l]
        l = list(liststr)
        #print liststr
        #print l
        huffmancode = dict()
        k = len(l)
        for i in range(k):
            #if i != k - 1:
            huffmancode[l[i]] = [1] * i + [0]
            #else:
                #huffmancode[l[i]] = [1] * 1    #because of the trap status,must keep the posion of it
        return huffmancode

    def NewGenerateCode(self,liststr):
        '''
        The Original function can't coding correctly.
        '''
        l = liststr.items()
        l.append(('\x00',0))      #the trap state
        tdict = dict()
        ndict = dict()
        m = len(l)
        kadd = list()  #to record the intermediate node
        kflag = str(m)
        while len(l) > 1:        #if the l is not null
            k = list()
            l.sort(key = lambda e:e[1])
            if (l[0][0] not in kadd) and (l[1][0] in kadd):
                k.append(l.pop(0))
                k.append(l.pop(0))
            elif (l[0][0] in kadd) and (l[1][0] in kadd):
                if l[0][0] == kflag:
                    k.append(l.pop(0))
                    k.append(l.pop(0))
                    k.reverse()
                else:
                    k.append(l.pop(0))
                    k.append(l.pop(0))
            else:
                k.append(l.pop(0))
                k.append(l.pop(0))
                k.reverse()
            for j in range(2):     #record the rle
                tdict[k[j][0]] = str(j)
            ndict[str(m)] = (k[0][0],k[1][0])
            if (k[0][0] == kflag) or (k[1][0] == kflag):
                kflag = str(m)      #record the position of '\x00'
            kadd.append(str(m))
            l.append((str(m),k[0][1] + k[1][1]))
            m += 1
        flag = str(m - 1)

        kl = sorted(list(ndict),key = lambda e:int(e),reverse = True)
        for i in kl:
            for j in ndict[i]:
                if i != flag:
                    tdict[j] = tdict[i] + tdict[j]
        kadd.pop(kadd.index(flag))
        for i in kadd:
            tdict.pop(i)
        return tdict

    def Encoding(self,Instr):
        '''
        Encode a str
        '''
        Instr = Instr[:-1]
        keys = list(set(Instr))         #get all the keys except flag'\0'
        liststr = dict()
        for i in keys:
            liststr[i] = Instr.count(i)         #get the total of the characters
        #dictmp = DictOperate()

        #l = dictmp.sortDic(liststr,1,True)      #get the key list in order
        #keystr = reduce(lambda x, y:x+y[0],l,'')
        #hmc = self.GenerateCode(keystr)        #get the huffman code,drop an eye on the parameters,ensure the value is property.

        hmc1 = self.NewGenerateCode(liststr)
        hmc = dict()
        #print hmc1
        for (i,j) in hmc1.items():
            hmc[i] = [int(k) for k in list(j)]

        outlist = []
        for i in Instr:
            outlist.extend(hmc[i])
        fo = FileOperate()
        k = len(outlist) % 8
        if k != 0:               #if the bits can't divided by 8 should do something.
            outlist.extend([1 for i in range(8 - k)])
        bytestr = fo.BitsToBytes(outlist)       #get the str
        return pickle.dumps(hmc1) + '\x00' + bytestr   #revers the keyword

    def Decoding(self,Instr):
        '''
        Decode a str
        '''
        #posf = Instr.find('\0')     #find the end flag of the key str
        posf = Instr.find('\x00')
        if posf == -1:
            return False
        #keys = Instr[:posf]         #get the keys words
        keys = pickle.loads(Instr[:posf])
        #print keys
        #keys = keys[:0:-1]          #get the right str
        #autotable = self.autoMachine(keys)
        autotable = self.NewAutoMachine(keys)
        #print autotable
        #Instr = Instr[posf + 1 :]   #get the coding str
        Instr = Instr[posf + 1 :]
        fo = FileOperate()
        bitslist = fo.BytesToBits(Instr)    #get the bits list
        state = 0                #first state
        outstr = ''
        for i in bitslist:
            state = autotable[state][i]
            if isinstance(autotable[state],list):
                outstr += autotable[state][1]
                state = autotable[state][2]
        else:
            pass        #if the bits has filling it will be ignored
        return outstr + '\0'        #restore the '\0'


    def autoMachine(self,keys):
        '''
        Create the autoMachine.
        '''
        autotable = dict()
        k = len(keys)
        for i in range(2 * k + 1):
            if i < k:
                autotable[i] = {0:2 * k - i,1:i + 1}
            elif i == k:
                autotable[i] = {0:k,1:k}        #trap
            else:
                autotable[i] = [-1,keys[i - k - 1],0]
        return autotable

    def NewAutoMachine(self,mdict):
        '''
        the decode automachine.just like a binary tree.
        '''
        orderid = 1
        autodic = dict()
        for (i,j) in mdict.items():
            nstat = 0
            for k in range(len(j)):
                if not autodic.has_key(nstat):
                    autodic[nstat] = dict()
                    autodic[nstat][int(j[k])] = orderid
                    nstat = orderid
                    orderid += 1        #record the status
                else:
                    if autodic[nstat].has_key(int(j[k])):
                        nstat = autodic[nstat][int(j[k])]
                    else:
                        autodic[nstat][int(j[k])] = orderid
                        nstat = orderid
                        orderid += 1
            else:
                if i == '\x00':
                    autodic[nstat] = {0:nstat,1:nstat}
                else:
                    autodic[nstat] = [-1,i,0]       #end status
                #orderid += 1
        return autodic

    def test4(self):
        k = {'x1':0.4,'x2':0.18,'x3':0.1,'x4':0.1,'x5':0.07,'x6':0.06,'x7':0.05,'x8':0.04}
        c = self.NewGenerateCode(k)
        print c
        d = self.NewAutoMachine(c)
        print d

    def test(self):
        '''
        test this module!
        '''
        k = {'1':50,'2':20,'3':90,'4':10,'5':100}
        dictmp = DictOperate()
        l = dictmp.sortDic(k,1,True)
        lsk = ''
        for k in l:
            lsk += k[0]
            lsk += '\0'
        print lsk
        c = self.GenerateCode(lsk)
        print c

    def test2(self):
        '''
        test auto machine
        '''
        k='543210'
        c = self.autoMachine(k)
        print c

    def testDecode(self):
        '''
        test decode
        '''
        avf = open('out1.txt','rb')
        c = avf.read()
        avf.close()

        k = self.Decoding(c)
        avf = open('out2.txt','wb')
        avf.write(k)
        avf.flush()
        avf.close()

    def testall(self):
        '''
        testall
        '''
        avf = open('out2.txt','rb')
        c = avf.read()
        avf.close()

        b = self.Encoding(c)
        avf = open('he.txt','wb')
        avf.write(b)
        avf.flush()
        avf.close()

        c = self.Decoding(b)
        avf = open('00.txt','wb')
        avf.write(c)
        avf.flush()
        avf.close()

if __name__ == '__main__':
    c = Huffman()
    #c.testDecode()
    #c.test2()
    #c.testall()
    c.test4()

